Developer CD Series 1996 June: Reference Library/Dev.CD Jun 96 RL/Dev.CD Jun 96 RL.toast/Technical Documentation/develop/develop Issue 24/develop Issue 24 code/Scriptable Database 1.0a15/Database/DBRecord.cp

Text File | 1996-04-25 | 49.9 KB | 1,528 lines | [TEXT/CWIE]

//================================================================================
// Greg Anderson
// db+
//
// Cursor to an database record
// 16 May 1994
// 31 Dec 1994
//
// Every database record is an entry in a balanced binary tree.  The
// exact type of tree used is an AVL tree (named after it inventors,
// G.M. Adelson-Velskii and E.M. Landis), as described in
// _Data Structures & Program Design_, (2nd edition) by R.L. Kruse,
// pp. 344-356.
//================================================================================

#include "DBRecord.h"

#include "Transaction.h"

#include "Exceptions.h"

#define INHERITED TAbstractRecord

//--------------------------------------------------------------------------------
// TDBRecord::~TDBRecord
//--------------------------------------------------------------------------------
TDBRecord::~TDBRecord()
{
} // TDBRecord::~TDBRecord

//--------------------------------------------------------------------------------
// TDBRecord::CompareTreeOrder
//--------------------------------------------------------------------------------
CompareEnumeration TDBRecord::CompareTreeOrder(TTransaction* t, AConst<TDBRecord> secondObject) const
{
    CompareEnumeration theOrder = this->CompareSortKeys(t, secondObject);
    if(theOrder == kObjectKeysEqual)
        theOrder = this->DetermineCompareEnumeration(this->RecordIndex(), secondObject->RecordIndex());
    return theOrder;
} // TDBRecord::CompareTreeOrder

//--------------------------------------------------------------------------------
// TDBRecord::FreeOwnedData
//--------------------------------------------------------------------------------
void TDBRecord::FreeOwnedData(TTransaction* t)
{
    //
    // If this entry contains any sub-elements, make them all free
    // (they will in turn free all of their sub-elements)
    //
    if(this->RecordCanHaveElements(t))
    {
        AConst<TDBRecord> elements = this->TopElementRecord(t);
        if(elements.Exists())
            (this->Transaction()->GetDBRecordUpdatePointer(elements))->FreeEntireTree(t);
    }

    //
    // If this entry contains any properties, make them all free
    // (they will in turn free all of their referenced data)
    //
    if(this->RecordCanHaveProperties(t))
    {
        AConst<TDBRecord> properties = this->TopPropertyRecord(t);
        if(properties.Exists())
            (this->Transaction()->GetDBRecordUpdatePointer(properties))->FreeEntireTree(t);
    }

    INHERITED::FreeOwnedData(t);
} // TDBRecord::FreeOwnedData

//--------------------------------------------------------------------------------
// TDBRecord::FreeThisRecord
//--------------------------------------------------------------------------------
void TDBRecord::FreeThisRecord(TTransaction* t)
{
    //
    // If this record is part of a tree, then remove it
    //
    if(this->RecordIsInATree(t))
        this->RemoveFromTree(t);

    INHERITED::FreeThisRecord(t);
} // TDBRecord::FreeThisRecord

//--------------------------------------------------------------------------------
// TDBRecord::FreeEntireTree
//
// This is a DANGEROUS routine; it frees this record and all of its siblings!
// Usually, you won't want to call it directly; see
// TDBRecord::FreeThisRecord.
//
// NOTE:  No effort is made to remove any existing references to this tree;
// it is assumed that the caller will do that before deleting the tree.
//--------------------------------------------------------------------------------
void TDBRecord::FreeEntireTree(TTransaction* t)
{
    //
    // We could just use an iterator, but it would be inefficient to
    // call RemoveCurrent on every node when we are just trying to
    // delete everything anyway.
    //
    AConst<TDBRecord> current = this->FirstItemInSubTree(t);
    while(current.Exists())
    {
        AConst<TDBRecord> next;

        //
        // If 'current' has children, then go down
        // to the last child in the tree and do nothing
        // else this iteration
        //
        if(current->HasLeftSibling(t))
            next = current->FirstItemInSubTree(t);
        else if(current->HasRightSibling(t))
            next = current->LastItemInSubTree(t);
        //
        // If 'current' has no children, then free it
        //
        else
        {
            //
            // The first thing to do is to go up to the
            // parent and remove the link that points to
            // the record we are deleting.  Once the node
            // to be deleted has been snipped from the tree,
            // we delete it.
            //
            next = current->ParentSibling(t);
            if(next.Exists())
            {
                ChildIdentifier whichChild = next->IdentifyChild(t, current);
                (this->Transaction()->GetDBRecordUpdatePointer(next))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(nil), whichChild);
            }
            //
            // Set the parent sibling of the current node to 'nil'
            // so that it will not be removed from the tree when
            // we call 'FreeThisRecord' (since we just removed
            // it manually).
            //
            (this->Transaction()->GetDBRecordUpdatePointer(current))->SetParentSibling(t, nil);
            (this->Transaction()->GetDBRecordUpdatePointer(current))->FreeThisRecord(t);
        }

        //
        // We're done with the current node (for now... if it had
        // children, we'll come back to it later); go on to the 'next' node.
        //
        current = next;
    }
} // TDBRecord::FreeEntireTree

//--------------------------------------------------------------------------------
// TDBRecord::IdentifyChild
//
// Determine how 'testChild' is linked to this record, or return
// 'kNodeIsNotAChild' if it is not.
//--------------------------------------------------------------------------------
ChildIdentifier TDBRecord::IdentifyChild(TTransaction* t, AConst<TDBRecord> testChild) const
{
    Require(testChild.Exists());

    ChildIdentifier childID = kNodeIsNotAChild;
    long testChildIndex = testChild->RecordIndex();

    //
    // Find a link that points to the testChild
    //
    if(this->LeftSiblingIndex(t) == testChildIndex)
        childID = kNodeIsLeftChild;
    else if(this->RightSiblingIndex(t) == testChildIndex)
        childID = kNodeIsRightChild;
    else if(this->RecordCanHaveElements(t) && (this->TopChildIndex(t) == testChildIndex))
        childID = kNodeIsTopOfElementTree;
    else if(this->RecordCanHaveProperties(t) && (this->TopPropertyIndex(t) == testChildIndex))
        childID = kNodeIsTopOfPropertyTree;

    //
    // Make sure that the 'testChild' is marked as being
    // at the top of the tree if it is in a 'top of tree'
    // pointer, and make sure that it is not marked as being
    // at the top of the tree if it is not.
    //
    if((childID == kNodeIsLeftChild) || (childID == kNodeIsRightChild))
        Require(testChild->RecordIsAtTopOfTree(t) == false);
    if((childID == kNodeIsTopOfElementTree) || (childID == kNodeIsTopOfPropertyTree))
        Require(testChild->RecordIsAtTopOfTree(t) == true);

    return childID;
} // TDBRecord::IdentifyChild

//--------------------------------------------------------------------------------
// TDBRecord::DeepestSubtree
//
// Debugging function only
//--------------------------------------------------------------------------------
long TDBRecord::DeepestSubtree(TTransaction* t) const
{
    long leftDepth = 0;
    AConst<TDBRecord> left = this->LeftSibling(t);
    if(left.Exists())
    {
        leftDepth = 1 + left->DeepestSubtree(t);
    }
    long rightDepth = 0;
    AConst<TDBRecord> right = this->RightSibling(t);
    if(right.Exists())
    {
        rightDepth = 1 + right->DeepestSubtree(t);
    }

    return rightDepth > leftDepth ? rightDepth : leftDepth;
} // TDBRecord::DeepestSubtree

//--------------------------------------------------------------------------------
// TDBRecord::Verify
//--------------------------------------------------------------------------------
void TDBRecord::Verify(TTransaction* t, Boolean verifyDeep /* = false */) const
{
    if(    (this->RecordIndex() == this->ParentSiblingIndex(t)) ||
        (this->RecordIndex() == this->LeftSiblingIndex(t)) ||
        (this->RecordIndex() == this->RightSiblingIndex(t)) )
        DebugStr("\ppTDBRecord::Verify record points at itself!");

    //
    // First check out the parent sibling link
    //
    AConst<TDBRecord> parent = this->LiteralParentSibling(t);
    if(parent.Exists())
    {
        if(parent->IdentifyChild(t, AConst<TDBRecord>(this)) == kNodeIsNotAChild)
            DebugStr("\pTDBRecord::Verify parent doesn't point back");
    }

    //
    // Next check left and right siblings
    //
    AConst<TDBRecord> left = this->LeftSibling(t);
    if(left.Exists())
    {
        if(left->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
            DebugStr("\pTDBRecord::Verify left sibling doesn't point back");
    }
    AConst<TDBRecord> right = this->RightSibling(t);
    if(right.Exists())
    {
        if(right->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
            DebugStr("\pTDBRecord::Verify right sibling doesn't point back");
    }

    //
    // In deep verifies, we recursively verify the left and right
    // children, and we also test the tree order of this nodes
    // predecessor and successor, and check out the node's balance factor.
    //
    if(verifyDeep)
    {
        if(left.Exists())
            left->Verify(t, verifyDeep);
        if(right.Exists())
            right->Verify(t, verifyDeep);

#if 0
        //
        // Test the ordering of the elements in the tree
        // (note: elements are sometimes temporarily mis-ordered,
        // then are put back into order, hense the #if 0)
        //
        AConst<TDBRecord> predecessor = this->PreviousItemInTree(t);
        if(predecessor.Exists())
        {
            if(this->CompareTreeOrder(t, predecessor) != kSecondObjectComesBefore)
                DebugStr("\pRecord should go before its predecessor!");
        }
        AConst<TDBRecord> successor = this->NextItemInTree(t);
        if(successor.Exists())
        {
            if(this->CompareTreeOrder(t, successor) != kSecondObjectComesAfter)
                DebugStr("\pRecord should come after its successor!");
        }
#endif

        //
        // Finally, test the recorded balance factor against reality
        //
        long leftDepth = 0;
        if(left.Exists())
            leftDepth = 1 + left->DeepestSubtree(t);
        long rightDepth = 0;
        if(right.Exists())
            rightDepth = 1 + right->DeepestSubtree(t);
        if((rightDepth - leftDepth > 1) || (rightDepth - leftDepth < -1))
            DebugStr("\ppTDBRecord::Verify tree balance factor greater than one");
        else switch(this->BalanceFactor(t))
        {
            case kSubtreesBalanced:
                if(rightDepth != leftDepth)
                    DebugStr("\pSubtree marked balanced when it isn't");
                break;
            case kLeftSideHigher:
                if(rightDepth >= leftDepth)
                    DebugStr("\pSubtree marked left-heavy when it isn't");
                break;
            case kRightSideHigher:
                if(rightDepth <= leftDepth)
                    DebugStr("\pSubtree marked right-heavy when it isn't");
                break;
            default:
                DebugStr("\pBalance factor set to unknown value");
        }
    }
} // TDBRecord::Verify

//--------------------------------------------------------------------------------
// TDBRecord::TopOfTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::TopOfTree(TTransaction* t) const
{
    AConst<TDBRecord> treeTop = AConst<TDBRecord>(this);

    while((treeTop->RecordIsInATree(t)) && (treeTop->RecordIsAtTopOfTree(t) == false))
        treeTop = treeTop->LiteralParentSibling(t);

    Require(treeTop.Exists());

    return treeTop;
} // TDBRecord::TopOfTree

//--------------------------------------------------------------------------------
// TDBRecord::TreeOwner
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::TreeOwner(TTransaction* t) const
{
    AConst<TDBRecord> treeTop = this->TopOfTree(t);
    AConst<TDBRecord> owner(nil);

    if(treeTop.Exists())
    {
        owner = treeTop->LiteralParentSibling(t);
    }

    return owner;
} // TDBRecord::TreeOwner

//--------------------------------------------------------------------------------
// TDBRecord::GoUpUntil
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::GoUpUntil(TTransaction* t, ChildIdentifier fromDirection) const
{
    AConst<TDBRecord> cameFrom = AConst<TDBRecord>(this);
    AConst<TDBRecord> upTo = cameFrom->ParentSibling(t);

    while((upTo.Exists()) && (upTo->IdentifyChild(t, cameFrom) != fromDirection))
    {
        cameFrom = upTo;
        upTo = cameFrom->ParentSibling(t);
    }

    return upTo;
} // TDBRecord::GoUpUntil

//--------------------------------------------------------------------------------
// TDBRecord::FirstItemInTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::FirstItemInTree(TTransaction* t) const
{
    AConst<TDBRecord> topOfTree = this->TopOfTree(t);
    AConst<TDBRecord> firstItemInTree = topOfTree->FirstItemInSubTree(t);

    return firstItemInTree;
} // TDBRecord::FirstItemInTree

//--------------------------------------------------------------------------------
// TDBRecord::LastItemInTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::LastItemInTree(TTransaction* t) const
{
    AConst<TDBRecord> topOfTree = this->TopOfTree(t);
    AConst<TDBRecord> lastItemInTree = topOfTree->LastItemInSubTree(t);

    return lastItemInTree;
} // TDBRecord::LastItemInTree

//--------------------------------------------------------------------------------
// TDBRecord::FindItemInTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::FindItemInTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
{
    AConst<TDBRecord> topOfTree = this->TopOfTree(t);
    AConst<TDBRecord> foundItem = topOfTree->FindItemInSubTree(t, doCompare);

    return foundItem;
} // TDBRecord::FindItemInTree

//--------------------------------------------------------------------------------
// TDBRecord::NumberOfChildSiblings
//--------------------------------------------------------------------------------
long TDBRecord::NumberOfChildSiblings(TTransaction* t) const
{
    long childSiblings = 0;

    AConst<TDBRecord> left = this->LeftSibling(t);
    AConst<TDBRecord> right = this->RightSibling(t);

    if(left.Exists())
        childSiblings += left->NumberOfChildSiblings(t) + 1;
    if(right.Exists())
        childSiblings += right->NumberOfChildSiblings(t) + 1;

    return childSiblings;
}

//--------------------------------------------------------------------------------
// TDBRecord::FirstItemInSubTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::FirstItemInSubTree(TTransaction* t) const
{
    AConst<TDBRecord> firstItem = AConst<TDBRecord>(this);

    while(firstItem->HasLeftSibling(t))
    {
        firstItem = firstItem->LeftSibling(t);
    }
    return firstItem;
} // TDBRecord::FirstItemInSubTree

//--------------------------------------------------------------------------------
// TDBRecord::LastItemInSubTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::LastItemInSubTree(TTransaction* t) const
{
    AConst<TDBRecord> lastItem = AConst<TDBRecord>(this);

    while(lastItem->HasRightSibling(t))
    {
        lastItem = lastItem->RightSibling(t);
    }
    return lastItem;
} // TDBRecord::LastItemInSubTree

//--------------------------------------------------------------------------------
// TDBRecord::NextItemInTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::NextItemInTree(TTransaction* t) const
{
    AConst<TDBRecord> nextItem = this->RightSibling(t);

    //
    // If there is a node in our RightSibling slot, then
    // the next node in the tree can be found by going down
    // one step to the right, and then following the left
    // links all the way to the end.
    //
    if(nextItem.Exists())
    {
        nextItem = nextItem->FirstItemInSubTree(t);
    }
    //
    // If there isn't an entry in our RightSibling slot,
    // then the next node in the tree is somewhere above
    // us (or we've come to the end of the tree and should
    // return nil--one or the other).
    //
    else
    {
        nextItem = this->GoUpUntil(t, kNodeIsLeftChild);
    }

    return nextItem;
} // TDBRecord::NextItemInTree

//--------------------------------------------------------------------------------
// TDBRecord::PreviousItemInTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::PreviousItemInTree(TTransaction* t) const
{
    AConst<TDBRecord> previousItem = this->LeftSibling(t);

    //
    // If there is a node in our LeftSibling slot, then
    // the previous node in the tree can be found by going down
    // one step to the left, and then following the right
    // links all the way to the end.
    //
    if(previousItem.Exists())
    {
        previousItem = previousItem->LastItemInSubTree(t);
    }
    //
    // If there isn't an entry in our LeftSibling slot,
    // then the previous node in the tree is somewhere above
    // us (or we've come to the beginning of the tree and should
    // return nil--one or the other).
    //
    else
    {
        previousItem = this->GoUpUntil(t, kNodeIsRightChild);
    }

    return previousItem;
} // TDBRecord::PreviousItemInTree

//--------------------------------------------------------------------------------
// TDBRecord::FindItemInSubTree
//--------------------------------------------------------------------------------
AConst<TDBRecord> TDBRecord::FindItemInSubTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
{
    REQUIREVALIDPOINTER(doCompare);

    AConst<TDBRecord> testRecord = AConst<TDBRecord>(this);

    while(testRecord.Exists())
    {
        CompareEnumeration theTest = doCompare->TestObject(t, testRecord);
        if(theTest != kObjectKeysEqual)
        {
            //
            // If the second object (the object being examined)
            // comes after the search key, then we'll find the
            // search key somewhere down the left side of the tree
            // (which is where the smaller items are found)
            //
            if(theTest == kSecondObjectComesAfter)
                testRecord = testRecord->LeftSibling(t);
            else if(theTest == kSecondObjectComesBefore)
                testRecord = testRecord->RightSibling(t);
        }
        else
            break;
    }

    return testRecord;
} // TDBRecord::FindItemInSubTree

//--------------------------------------------------------------------------------
// TDBRecord::Insert
//--------------------------------------------------------------------------------
Boolean TDBRecord::Insert(TTransaction* t, AnUpdate<TDBRecord> insertThis)
{
    Boolean treeGrewTaller = false;

    Require(insertThis->RecordIsInATree(t) == false);
    Require((insertThis->HasRightSibling(t) == false) && (insertThis->HasLeftSibling(t) == false));

    //
    // Case 1:  Insert to the right
    //
    if(this->CompareTreeOrder(t, insertThis) == kSecondObjectComesAfter)
    {
        //
        // We want to insert the node to the right; if there's nothing
        // to the right, then we can just fill in the empty slot
        //
        if(this->HasRightSibling(t) == false)
        {
            ASSERT(this->BalanceFactor(t) != kRightSideHigher);

            insertThis->SetRecordIsAtTopOfTree(t, false);
            insertThis->SetParentSibling(t, this);
            insertThis->SetBalanceFactor(t, kSubtreesBalanced);
            this->SetRightSibling(t, insertThis);

            //
            // The right subtree was empty; now it has one node.
            //
            treeGrewTaller = true;
        }
        //
        // If there's already something to the right, then
        // we need to make a recursive call to insert
        //
        else
        {
            AConst<TDBRecord> rightChild = this->RightSibling(t);
            treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(rightChild))->Insert(t, insertThis);
        }

        //
        // At this point we know that we inserted a node
        // somewhere on the right branch.  'treeGrewTaller'
        // is true if the right subtree grew taller, false
        // if it stayed the same height.  The node was balanced
        // before the insert, so if the right subtree did not
        // change in height, then we know that this node is
        // still balanced.
        //
        if(treeGrewTaller)
        {
            switch(this->BalanceFactor(t))
            {
                //
                // If this node was balanced and the right side just
                // grew taller, then mark this node as being right-heavy
                // and note that this subtree has grown taller.
                //
                case kSubtreesBalanced:
                {
                    this->SetBalanceFactor(t, kRightSideHigher);
                    treeGrewTaller = true;
                    break;
                }
                //
                // If the left side of this tree used to be one
                // node taller than the right, and the right subtree
                // just grew taller by one, then mark this node as
                // being balanced and note that this tree did not
                // grow any taller.
                //
                case kLeftSideHigher:
                {
                    this->SetBalanceFactor(t, kSubtreesBalanced);
                    treeGrewTaller = false;
                    break;
                }

                //
                // If the right subtree was already taller than
                // the left subtree, and the right side grew again,
                // then we need to do a right-side balance.
                //
                case kRightSideHigher:
                {
                    this->RightBalance(t);
                    treeGrewTaller = false;
                    break;
                }
            }
        }
#if SLOWDEBUG
        //
        // The tree above us may need to be balanced,
        // but at this point this subtree should verify.
        //
        this->Verify(t, true);
#endif
    }
    //
    // Case 2:  Insert to the left
    //
    else
    {
        if(this->HasLeftSibling(t) == false)
        {
            ASSERT(this->BalanceFactor(t) != kLeftSideHigher);
            insertThis->SetRecordIsAtTopOfTree(t, false);
            insertThis->SetParentSibling(t, this);
            insertThis->SetBalanceFactor(t, kSubtreesBalanced);
            this->SetLeftSibling(t, insertThis);
            treeGrewTaller = true;
        }
        else
        {
            AConst<TDBRecord> leftChild = this->LeftSibling(t);
            treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(leftChild))->Insert(t, insertThis);
        }
        if(treeGrewTaller)
        {
            switch(this->BalanceFactor(t))
            {
                case kSubtreesBalanced:
                {
                    this->SetBalanceFactor(t, kLeftSideHigher);
                    treeGrewTaller = true;
                    break;
                }
                case kRightSideHigher:
                {
                    this->SetBalanceFactor(t, kSubtreesBalanced);
                    treeGrewTaller = false;
                    break;
                }
                case kLeftSideHigher:
                {
                    this->LeftBalance(t);
                    treeGrewTaller = false;
                    break;
                }
            }
        }
#ifdef SLOWDEBUG
        this->Verify(t, true);
#endif
    }

    return treeGrewTaller;
} // TDBRecord::Insert


//--------------------------------------------------------------------------------
// TDBRecord::RemoveFromTree
//--------------------------------------------------------------------------------
void TDBRecord::RemoveFromTree(TTransaction* t)
{
    //
    // Don't do anything unless we're part of a tree
    //
    if(this->RecordIsInATree(t))
    {
#if 0
        //
        // Before we do anything, verify that everything in
        // this tree is valid
        //
        // Note:  Sometimes this will cause assertions to
        // fire; for example, if the item is being removed
        // from ResortThisRecord, then verify will report
        // that the tree is not sorted correctly
        //
        AConst<TDBRecord> treeTop = this->TopOfTree(t);
        treeTop->Verify(t, true);
#endif

        //
        // If this node has two children, then we need to swap its
        // position in the tree with its immediate predecessor, found
        // by stepping down to the left once and then walking as far to
        // the right as possible.  This changes the order of the tree
        // temporarily (this item and its previous item are now out
        // of order), but once this item is removed all items remaining
        // in the tree will be in the correct order.
        //
        if((this->HasRightSibling(t) == true) && (this->HasLeftSibling(t) == true))
        {
            AConst<TDBRecord> swapNode = this->PreviousItemInTree(t);
            this->SwapTreePositions(t, this->Transaction()->GetDBRecordUpdatePointer(swapNode));
#ifdef SLOWDEBUG
            this->TopOfTree(t)->Verify(t, true);
#endif
        }

        //
        // Remember our parent node before we put our child into the
        // slot we used to occupy (since we might not have a child, and
        // we don't want to loose our reference to the parent)
        //
        AConst<TDBRecord> balancePoint = this->ParentSibling(t);

        //
        // Now that we have zero or one children, move up our
        // child list to the slot that we are vacating.
        // If we don't have any children, then don't bother
        // to do the move.
        //
        AConst<TDBRecord> moveUp(nil);
        if(this->HasLeftSibling(t) == true)
        {
            moveUp = this->LeftSibling(t);
            this->SetLeftSibling(t, nil);
        }
        else if(this->HasRightSibling(t) == true)
        {
            moveUp = this->RightSibling(t);
            this->SetRightSibling(t, nil);
        }

        //
        // Make the parent of 'moveUp' be the parent of
        // this node; at this point, 'this' shouldn't have
        // any references inside this tree--it has been
        // completely removed.  All that remains to be done
        // is to rebalance the AVL tree.
        //
        // n.b. If 'moveUp' is nil, then SetParentsLinkTothisNodeTo
        // will nil out the parents link to this node
        //
        ChildIdentifier    deletedFromSide = this->SetParentsLinkToThisNodeTo(t, moveUp);
#ifdef SLOWDEBUG
        if(moveUp.Exists())
        {
            moveUp->Verify(t, true);
        }
#endif

        //
        // 'deletedFromSide' will almost always be 'left child' or
        // 'right child'.  The only exception is if we just removed
        // the root of the tree, which is only possible in a two-node
        // tree (otherwise the root would have been swapped with
        // some leaf node, and we would be removing a leaf, not the root).
        //
        if((deletedFromSide == kNodeIsLeftChild) || (deletedFromSide == kNodeIsRightChild))
        {
            //
            // Keep fixing up the balancing of the tree until we
            // get a point where the tree is longer on the other
            // branch (the one we didn't delete from); at that
            // point we can mark the tree as balanced and stop
            // adjusting it.
            //
            Boolean treeBecameShorter = true;
            while((balancePoint.Exists()) && (treeBecameShorter == true))
            {
#ifdef SLOWDEBUG
                //
                // At this point in the execution of Remove, we know that
                // the balance point is unbalanced, but its children should
                // be okay
                //
                AConst<TDBRecord> verifyLeft = balancePoint->LeftSibling(t);
                if(verifyLeft.Exists())
                    verifyLeft->Verify(t, true);
                AConst<TDBRecord> verifyRight = balancePoint->RightSibling(t);
                if(verifyRight.Exists())
                    verifyRight->Verify(t, true);
#endif

                //
                // We must record which node we're planning on going to
                // next right away, because otherwise a tree rotation
                // could push 'balancePoint' down; if that happens, we
                // want to go up to the balance point's former parent,
                // not its new parent.
                //
                AConst<TDBRecord> nextBalancePoint = balancePoint->ParentSibling(t);
                ChildIdentifier nextDeletedFromSide = kNodeIsNotAChild;
                if(nextBalancePoint.Exists())
                    nextDeletedFromSide = nextBalancePoint->IdentifyChild(t, balancePoint);

                //
                // Set 'testFactor' to the side we _didn't_ delete
                // from (if the balance point was exactly balanced,
                // we'll set its balance factor to this value)
                //
                long testFactor = ((deletedFromSide == kNodeIsLeftChild) ? kRightSideHigher : kLeftSideHigher);

                //
                // Case 1:  Removing a node from a balanced subtree.
                //            Mark the tree unbalanced, and we're done
                //
                if(balancePoint->BalanceFactor(t) == kSubtreesBalanced)
                {
                    (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, testFactor);
                    treeBecameShorter = false;
                }
                //
                // Case 2:    Removing a node from the longer side of
                //            an unbalanced subtree.  Mark the tree balanced,
                //            but keep going.
                //
                else if(balancePoint->BalanceFactor(t) != testFactor)
                {
                    (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
                    treeBecameShorter = true;
                }
                //
                // Case 3:    Removing a node from the shorter side of an
                //            unbalanced subtree.  Rotations are necessary
                //            to bring the tree back into alignment
                //
                else
                {
                    AConst<TDBRecord> tallerSubtree = (deletedFromSide == kNodeIsLeftChild) ? balancePoint->RightSibling(t) : balancePoint->LeftSibling(t);
                    Require(tallerSubtree.Exists());

                    //
                    // Case 3a:    Taller subtree is balanced
                    //
                    if(tallerSubtree->BalanceFactor(t) == kSubtreesBalanced)
                    {
                        if(deletedFromSide == kNodeIsLeftChild)
                        {
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kRightSideHigher);
                            (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kLeftSideHigher);
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
                        }
                        else
                        {
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kLeftSideHigher);
                            (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kRightSideHigher);
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
                        }
                        treeBecameShorter = false;
                    }
                    //
                    // Case 3b:    Taller subtree has the same balance
                    //            factor as the balance point
                    //
                    else if(tallerSubtree->BalanceFactor(t) == balancePoint->BalanceFactor(t))
                    {
                        (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
                        (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
                        if(deletedFromSide == kNodeIsLeftChild)
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
                        else
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
                        treeBecameShorter = true;
                    }
                    //
                    // Case 3c:    Taller subtree has a different balance
                    //            factor than the balance point
                    //
                    else
                    {
                        if(deletedFromSide == kNodeIsLeftChild)
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateRightSide(t);
                        else
                            (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateLeftSide(t);
                        treeBecameShorter = true;
                    }
                }

#ifdef SLOWDEBUG
                //
                // The balance point should now verify; if the balance
                // point was moved down, though, then its parent should
                // also be balanced.
                //
                AConst<TDBRecord> balancePointsNewParent = balancePoint->ParentSibling(t);
                if((balancePointsNewParent.Exists() == false) || (nextBalancePoint.Exists() == false) || (balancePointsNewParent->RecordIndex() == nextBalancePoint->RecordIndex()))
                    balancePoint->Verify(t, true);
                else
                    balancePointsNewParent->Verify(t, true);
#endif

                //
                // Go up to the next node of the tree.  Stop if we
                // hit the top, or if treeBecameShorter is set to false
                //
                balancePoint = nextBalancePoint;
                deletedFromSide = nextDeletedFromSide;
            }
        }

        //
        // Finally, nil out our parent-sibling link, since we're
        // not part of any tree any longer.  Make sure that we
        // really don't have any left or right child references,
        // and set the bits that indicate that this node is at
        // the top of a tree, and it's subtrees are balanced (which
        // is what an unattached childless node should look like)
        //
        this->SetParentSibling(t, nil);
        if((this->HasRightSibling(t) == true) || (this->HasLeftSibling(t) == true))
            DebugStr("\pOh oh, child sibling links still exist in TDBRecord::RemoveFromTree");
        this->SetRecordIsAtTopOfTree(t, true);
        this->SetBalanceFactor(t, kSubtreesBalanced);
    }
} // TDBRecord::RemoveFromTree

//--------------------------------------------------------------------------------
// TDBRecord::ResortThisRecord
//
// The method "ResortThisRecord" should be called whenever the sort key
// for this record changes; doing that removes and re-inserts this record
// in the tree it is currently contained in.
//--------------------------------------------------------------------------------
void TDBRecord::ResortThisRecord(TTransaction* t)
{
    //
    // Hang onto a reference to some other element in
    // the same tree that we're in
    //
    AConst<TDBRecord> someOtherRecord = this->ParentSibling(t);
    if(someOtherRecord.Exists() == false)
        someOtherRecord = this->LeftSibling(t);
    if(someOtherRecord.Exists() == false)
        someOtherRecord = this->RightSibling(t);

    //
    // If this is the only record in the tree, then we
    // don't need to resort.
    //
    // Note:  It might be worthwhile to look at the
    // previous and next items in the tree, and only
    // do a resort if this item really does need to
    // move away from its current location.
    //
    if(someOtherRecord.Exists())
    {
        //
        // Remove this entry from the tree, then find the new top-of-tree record
        //
        this->RemoveFromTree(t);
        AConst<TDBRecord> topOfTree = someOtherRecord->TopOfTree(t);
#ifdef SLOWDEBUG
        this->Verify(t);
        topOfTree->Verify(t, true);
#endif

        //
        // Reinsert this element back into the tree.
        //
        (this->Transaction()->GetDBRecordUpdatePointer(topOfTree))->Insert(t, this);
#ifdef SLOWDEBUG
        this->Verify(t);
        this->TopOfTree(t)->Verify(t, true);
#endif
    }
} // TDBRecord::ResortThisRecord

//--------------------------------------------------------------------------------
// TDBRecord::RightBalance
//
// Assumptions:  A node was just inserted on the right side of this tree, and
// it made the subtree grow taller.  There was already at least one node on
// the right side before the insertion.
//--------------------------------------------------------------------------------
void TDBRecord::RightBalance(TTransaction* t)
{
    AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
    Require(rootOfRightSubtree.Exists());

    switch(rootOfRightSubtree->BalanceFactor(t))
    {
        case kRightSideHigher:
        {
            //
            // Do a left rotation
            //
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            this->SetBalanceFactor(t, kSubtreesBalanced);
            this->RotateLeft(t);
            break;
        }

        case kLeftSideHigher:
        {
            this->DoubleRotateRightSide(t);
            break;
        }

        case kSubtreesBalanced:
        {
            //
            // This should never happen
            //
            Require(false);
            this->Verify(t, true);
            break;
        }
    }
} // TDBRecord::RightBalance

//--------------------------------------------------------------------------------
// TDBRecord::LeftBalance
//
// Assumptions:  A node was just inserted on the left side of this tree, and
// it made the subtree grow taller.  There was already at least one node on
// the left side before the insertion.
//--------------------------------------------------------------------------------
void TDBRecord::LeftBalance(TTransaction* t)
{
    AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);

    switch(rootOfLeftSubtree->BalanceFactor(t))
    {
        case kLeftSideHigher:
        {
            //
            // Do a right rotation
            //
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            this->SetBalanceFactor(t, kSubtreesBalanced);
            this->RotateRight(t);
            break;
        }

        case kRightSideHigher:
        {
            this->DoubleRotateLeftSide(t);
            break;
        }

        case kSubtreesBalanced:
        {
            //
            // This should never happen
            //
            Require(false);
            this->Verify(t, true);
            break;
        }
    }
} // TDBRecord::LeftBalance

//--------------------------------------------------------------------------------
// TDBRecord::RotateLeft
//--------------------------------------------------------------------------------
void TDBRecord::RotateLeft(TTransaction* t)
{
    AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
    if(rootOfRightSubtree.Exists())
    {
        AConst<TDBRecord> leftChildOfRightSubtree = rootOfRightSubtree->LeftSibling(t);

        this->SetRightSibling(t, leftChildOfRightSubtree);
        if(leftChildOfRightSubtree.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(leftChildOfRightSubtree))->SetParentSibling(t, this);
        }
        this->SetParentsLinkToThisNodeTo(t, rootOfRightSubtree);
        (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetLeftSibling(t, this);
        this->SetParentSibling(t, rootOfRightSubtree);
    }
} // TDBRecord::RotateLeft

//--------------------------------------------------------------------------------
// TDBRecord::RotateRight
//--------------------------------------------------------------------------------
void TDBRecord::RotateRight(TTransaction* t)
{
    AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
    if(rootOfLeftSubtree.Exists())
    {
        AConst<TDBRecord> rightChildOfRightSubtree = rootOfLeftSubtree->RightSibling(t);

        this->SetLeftSibling(t, rightChildOfRightSubtree);
        if(rightChildOfRightSubtree.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(rightChildOfRightSubtree))->SetParentSibling(t, this);
        }
        this->SetParentsLinkToThisNodeTo(t, rootOfLeftSubtree);
        (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetRightSibling(t, this);
        this->SetParentSibling(t, rootOfLeftSubtree);
    }
} // TDBRecord::RotateLeft

//--------------------------------------------------------------------------------
// TDBRecord::DoubleRotateRightSide
//--------------------------------------------------------------------------------
void TDBRecord::DoubleRotateRightSide(TTransaction* t)
{
    AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
    Require(rootOfRightSubtree.Exists());
    AConst<TDBRecord> leftSiblingOfRootOfRight = rootOfRightSubtree->LeftSibling(t);
    Require(leftSiblingOfRootOfRight.Exists());

    switch(leftSiblingOfRootOfRight->BalanceFactor(t))
    {
        case kSubtreesBalanced:
        {
            this->SetBalanceFactor(t, kSubtreesBalanced);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            break;
        }

        case kLeftSideHigher:
        {
            this->SetBalanceFactor(t, kSubtreesBalanced);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kRightSideHigher);
            break;
        }

        case kRightSideHigher:
        {
            this->SetBalanceFactor(t, kLeftSideHigher);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            break;
        }
    }
    (this->Transaction()->GetDBRecordUpdatePointer(leftSiblingOfRootOfRight))->SetBalanceFactor(t, kSubtreesBalanced);
    (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->RotateRight(t);
    this->RotateLeft(t);
} // TDBRecord::DoubleRotateRightSide

//--------------------------------------------------------------------------------
// TDBRecord::DoubleRotateLeftSide
//--------------------------------------------------------------------------------
void TDBRecord::DoubleRotateLeftSide(TTransaction* t)
{
    AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
    Require(rootOfLeftSubtree.Exists());
    AConst<TDBRecord> rightSiblingOfRootOfLeft = rootOfLeftSubtree->RightSibling(t);
    Require(rightSiblingOfRootOfLeft.Exists());

    switch(rightSiblingOfRootOfLeft->BalanceFactor(t))
    {
        case kSubtreesBalanced:
        {
            this->SetBalanceFactor(t, kSubtreesBalanced);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            break;
        }

        case kRightSideHigher:
        {
            this->SetBalanceFactor(t, kSubtreesBalanced);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kLeftSideHigher);
            break;
        }

        case kLeftSideHigher:
        {
            this->SetBalanceFactor(t, kRightSideHigher);
            (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
            break;
        }
    }
    (this->Transaction()->GetDBRecordUpdatePointer(rightSiblingOfRootOfLeft))->SetBalanceFactor(t, kSubtreesBalanced);

    (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->RotateLeft(t);
    this->RotateRight(t);
} // TDBRecord::DoubleRotateLeftSide

//--------------------------------------------------------------------------------
// TDBRecord::InitializeNewRecord
//--------------------------------------------------------------------------------
void TDBRecord::InitializeNewRecord(TTransaction* t)
{
    Require(this->ThisRecordIsFree(t));

    this->SetParentSiblingIndex(t, kNilIndex);
    this->SetLeftSiblingIndex(t, kNilIndex);
    this->SetRightSiblingIndex(t, kNilIndex);
} // TDBRecord::InitializeNewRecord

//--------------------------------------------------------------------------------
// TDBRecord::PropertyValueChanged
//
// Whenever a property changes value, it informs the record that owns it by
// calling this method.
//--------------------------------------------------------------------------------
void TDBRecord::PropertyValueChanged(TTransaction*, AConst<TDBProperty> /*propertyThatChanged*/)
{
} // TDBRecord::PropertyValueChanged

//--------------------------------------------------------------------------------
// TDBRecord::RecordCanHaveElements
//
// This method must return 'true' if the record can contain elements.
//--------------------------------------------------------------------------------
Boolean TDBRecord::RecordCanHaveElements(TTransaction*) const
{
    return false;
} // TDBRecord::RecordCanHaveElements

//--------------------------------------------------------------------------------
// TDBRecord::RecordCanHaveProperties
//
// This method must return 'true' if the record can contain properties.
//--------------------------------------------------------------------------------
Boolean TDBRecord::RecordCanHaveProperties(TTransaction*) const
{
    return false;
} // TDBRecord::RecordCanHaveProperties

//--------------------------------------------------------------------------------
// TDBRecord::RequireRecordCanHaveElements
//
// This method will fail if the record cannot contain elements, or do nothing
// if it can.
//--------------------------------------------------------------------------------
void TDBRecord::RequireRecordCanHaveElements(TTransaction* t) const
{
    if(this->RecordCanHaveElements(t) == false)
         FailErr(eWrongDataType);
} // TDBRecord::RequireRecordCanHaveElements

//--------------------------------------------------------------------------------
// TDBRecord::RequireRecordCanHaveProperties
//
// This method will fail if the record cannot contain properties, or do nothing
// if it can.
//--------------------------------------------------------------------------------
void TDBRecord::RequireRecordCanHaveProperties(TTransaction* t) const
{
    if(this->RecordCanHaveProperties(t) == false)
         FailErr(eWrongDataType);
} // TDBRecord::RequireRecordCanHaveProperties

//--------------------------------------------------------------------------------
// TDBRecord::SetChildLinkOfNewParent
//--------------------------------------------------------------------------------
void TDBRecord::SetChildLinkOfNewParent(TTransaction* t, AConst<TDBRecord> newChild, ChildIdentifier whichChild)
{
    Boolean isAtTop = false;

    switch(whichChild)
    {
        case kNodeIsLeftChild:
            this->SetLeftSibling(t, newChild);
            break;

        case kNodeIsRightChild:
            this->SetRightSibling(t, newChild);
            break;

        case kNodeIsTopOfElementTree:
            isAtTop = true;
            this->SetElements(t, newChild);
            break;

        case kNodeIsTopOfPropertyTree:
            isAtTop = true;
            this->SetProperties(t, newChild);
            break;

        default:
            Throw(eLinksCorrupt);
    }

    //
    // It is possible that someone may want to set the child
    // link of the new parent to 'nil', in which case we won't
    // need to point the new child back to its new parent.
    //
    if(newChild.Exists())
    {
        AnUpdate<TDBRecord> newChildUpdate = this->Transaction()->GetDBRecordUpdatePointer(newChild);
        newChildUpdate->SetRecordIsAtTopOfTree(t, isAtTop);
        newChildUpdate->SetParentSibling(t, this);
    }
} // TDBRecord::SetChildLinkOfNewParent

//--------------------------------------------------------------------------------
// TDBRecord::SetParentsLinkToThisNodeTo
//
// This routine is called when 'newChild' is being rotated into the slot that
// this record formerly occupied.  It is the responsibility of this routine to
// insure that whichever node previously pointed to this record will
// thereafter always point to 'newChild' instead.
//--------------------------------------------------------------------------------
ChildIdentifier TDBRecord::SetParentsLinkToThisNodeTo(TTransaction* t, AConst<TDBRecord> newChild)
{
    AConst<TDBRecord> parentSibling = this->LiteralParentSibling(t);
    ChildIdentifier whichChild = kNodeIsNotAChild;

    if(parentSibling.Exists())
    {
        whichChild = parentSibling->IdentifyChild(t, this);
        (this->Transaction()->GetDBRecordUpdatePointer(parentSibling))->SetChildLinkOfNewParent(t, newChild, whichChild);
        this->SetParentSibling(t, nil);
        this->SetRecordIsAtTopOfTree(t, false);
    }

    return whichChild;
} // TDBRecord::SetParentsLinkToThisNodeTo

//--------------------------------------------------------------------------------
// TDBRecord::SwapTreePositions
//--------------------------------------------------------------------------------
void TDBRecord::SwapTreePositions(TTransaction* t, AnUpdate<TDBRecord> swapWith)
{
    //
    // The first step is to look up all of the adjacent
    // links for both nodes before changing anything
    //
    AConst<TDBRecord> thisLeftSibling = this->LeftSibling(t);
    AConst<TDBRecord> thisRightSibling = this->RightSibling(t);
    AConst<TDBRecord> thisParent = this->LiteralParentSibling(t);
    long thisBalanceFactor = this->BalanceFactor(t);
    AConst<TDBRecord> othersLeftSibling = swapWith->LeftSibling(t);
    AConst<TDBRecord> othersRightSibling = swapWith->RightSibling(t);
    AConst<TDBRecord> othersParent = swapWith->LiteralParentSibling(t);
    long otherBalanceFactor = swapWith->BalanceFactor(t);
    ChildIdentifier thisLinkage;
    ChildIdentifier othersLinkage;
    OSErr err = noErr;

    //
    // We really expect that this routine will be called on two
    // records that are both part of the same tree, but this is
    // not required; in fact, one of the records may not even
    // be in a tree.  The one thing that would be really really
    // bad would be to swap an element with a property; we should
    // test for this, but we currently do not.
    //
    // At any rate, it is very important to remember how the
    // nodes were linked before doing the special-checking for
    // swapping adjacent nodes.
    //
    if(thisParent.Exists())
        thisLinkage = thisParent->IdentifyChild(t, this);
    if(othersParent.Exists())
        othersLinkage = othersParent->IdentifyChild(t, swapWith);

    //
    // Next, we need to do special-checking for adjacent records
    // (gasp, hack)
    //
    if(thisLeftSibling.Exists() && (thisLeftSibling->RecordIndex() == swapWith->RecordIndex()))
    {
        Require(othersParent->RecordIndex() == this->RecordIndex());
        thisLeftSibling = this;
        othersParent = swapWith;
    }
    if(thisRightSibling.Exists() && (thisRightSibling->RecordIndex() == swapWith->RecordIndex()))
    {
        Require(othersParent->RecordIndex() == this->RecordIndex());
        thisRightSibling = this;
        othersParent = swapWith;
    }
    if(othersLeftSibling.Exists() && (othersLeftSibling->RecordIndex() == this->RecordIndex()))
    {
        Require(thisParent->RecordIndex() == swapWith->RecordIndex());
        othersLeftSibling = swapWith;
        thisParent = this;
    }
    if(othersRightSibling.Exists() && (othersRightSibling->RecordIndex() == this->RecordIndex()))
    {
        Require(thisParent->RecordIndex() == swapWith->RecordIndex());
        othersRightSibling = swapWith;
        thisParent = this;
    }

    Try
    {
        //
        // Relink other node
        //
        swapWith->SetLeftSibling(t, thisLeftSibling);
        swapWith->SetRightSibling(t, thisRightSibling);
        swapWith->SetBalanceFactor(t, thisBalanceFactor);
        if(thisParent.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(thisParent))->SetChildLinkOfNewParent(t, swapWith, thisLinkage);
            thisParent = nil;
        }
        else
            swapWith->SetParentSibling(t, nil);
        if(thisLeftSibling.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(thisLeftSibling))->SetParentSibling(t, swapWith);
            thisLeftSibling = nil;
        }
        if(thisRightSibling.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(thisRightSibling))->SetParentSibling(t, swapWith);
            thisRightSibling = nil;
        }

        //
        // Relink this node
        //
        this->SetLeftSibling(t, othersLeftSibling);
        this->SetRightSibling(t, othersRightSibling);
        this->SetBalanceFactor(t, otherBalanceFactor);
        if(othersParent.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(othersParent))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(this), othersLinkage);
            othersParent = nil;
        }
        else
            this->SetParentSibling(t, nil);
        if(othersLeftSibling.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(othersLeftSibling))->SetParentSibling(t, this);
        }
        if(othersRightSibling.Exists())
        {
            (this->Transaction()->GetDBRecordUpdatePointer(othersRightSibling))->SetParentSibling(t, this);
        }
    }
    Catch(err)
    {
        Throw(err);
    }
} // TDBRecord::SwapTreePositions

//================================================================================
// Class TAbstractRecordIterator
//================================================================================

//--------------------------------------------------------------------------------
// TAbstractRecordIterator::TAbstractRecordIterator
//--------------------------------------------------------------------------------
TAbstractRecordIterator::TAbstractRecordIterator(TTransaction* transaction, AConst<TDBRecord> cursor, Boolean direction /* = kIterateForward */)
{
    fCursor = cursor;
    fDirection = direction;
    fTransaction = transaction;
    this->Reset();
}

//--------------------------------------------------------------------------------
// TAbstractRecordIterator::Reset
//--------------------------------------------------------------------------------
void TAbstractRecordIterator::Reset(Boolean direction /* = kIterateForward */)
{
    fDirection = direction;
    fHaveRemovedCurrent = false;
    if(fCursor.Exists())
    {
        if(this->IterateForward())
            fCurrent = fCursor->FirstItemInTree(fTransaction);
        else
            fCurrent = fCursor->LastItemInTree(fTransaction);
    }
    else
        fCurrent = nil;
} // TAbstractRecordIterator::Reset

//--------------------------------------------------------------------------------
// TAbstractRecordIterator::~TAbstractRecordIterator
//--------------------------------------------------------------------------------
TAbstractRecordIterator::~TAbstractRecordIterator()
{
    if(fCurrent.Exists())
    {
        fCurrent = AConst<TDBRecord>(nil);
    }
} // TAbstractRecordIterator::~TAbstractRecordIterator

//--------------------------------------------------------------------------------
// TAbstractRecordIterator::Next
//--------------------------------------------------------------------------------
void TAbstractRecordIterator::Next()
{
    if(fCurrent.Exists() && (fHaveRemovedCurrent == false))
    {
        AConst<TDBRecord> next;

        if(this->IterateForward())
            next = fCurrent->NextItemInTree(fTransaction);
        else
            next = fCurrent->PreviousItemInTree(fTransaction);

        fCurrent = next;
    }

    fHaveRemovedCurrent = false;
} // TAbstractRecordIterator::Next

//--------------------------------------------------------------------------------
// TAbstractRecordIterator::RemoveCurrent
//--------------------------------------------------------------------------------
void TAbstractRecordIterator::RemoveCurrent()
{
    fHaveRemovedCurrent = false;
    AConst<TDBRecord> recordToRemove = fCurrent;
    if(recordToRemove.Exists())
    {
        this->Next();
        (fTransaction->GetDBRecordUpdatePointer(recordToRemove))->RemoveFromTree(fTransaction);
        fHaveRemovedCurrent = true;
    }
} // TAbstractRecordIterator::RemoveCurrent